package Greedy;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 0-1 背包问题
 * 问题描述：
 *      假设有n件物品，每件物品的重量为w[i],价值为v[i]
 *      现在我们有一个最大容量为W的背包，我们如何选取存放
 *      的物品使得我们可以装进背包物品的总价值最大？
 *      注意：每件物品只有一件，要么放进背包，要么不放进背包
 *
 * 如果采用贪心算法我们有三种贪心策略：
 *      1. 价值主导：每次从物品中选择价值最大的
 *      2. 重量主导：每次从物品中选择重量最轻的
 *      3. 价值密度主导：所谓的价值密度：密度 = 价值 / 重量(假设以g为单位)    每g物品的价值
 * 下面我们分别采用上述三种贪心策略来求解该问题，看看到底哪一个可以得到最优解
 *
 *
 */
@SuppressWarnings("all")
public class 背包问题 {
    public static void main(String[] args) {

    }

    /**
     * 以价值为主导: 每次从商品中选择价值最大的一件商品放入背包
     * @param weights：商品的重量数组
     * @param values：商品的价值数组
     * @param Weight：背包可以承受的总重量
     */
    public static void OrientedByValue(int[] weights,int[] values,int Weight) {
        Map<Integer,Integer> goods = new HashMap<>(); // 用于存放最终背包中的物品 key为商品重量，value为该商品的价值
        for (int i = 0; i < weights.length; i++) {
            goods.put(values[i],weights[i]); // 将物品的属性放到一个hashmap中
        }
        // 对hashmap进行排序 按照价值进行排序
        // 将上述的键换成value，值换成key
        
    }


}
